The current state-of-the-art within dental implantology is the use of implant planning software based on (CB)CT images of the patient's jaw and remaining dentition that allows diagnosis and implant planning in 3D. A typical second step is the transfer of the planned implant positions to the mouth of the patient by means of a surgical drilling template, which can be either tooth-, mucosa-, or bone-supported. In case of CAD-CAM tooth-supported drilling templates a high-resolution digital model of the patient's dentition is needed for the design and manufacturing of a well-fitting drilling template. Therefore a high-resolution model needs to be accurately registered/matched with the (CB)CT data of the patient's jaw. The high-resolution digital model of the patient's dentition can be obtained directly (e.g. intra-oral scan) or indirectly (e.g. optical or (CB)CT scan of plaster cast or impression).
Typical registration techniques are based on the ICP (Iterative Closest Points) algorithm and try to minimize the distance error between the two objects. These registration techniques work very well for “identical” objects, but not in case objects are by default only partially “identical”. In case of partially identical objects it is needed to first mark the identical parts in order to optimize the registration using ICP algorithms. These registration techniques also require a good starting position which is typically obtained by manually indicating some corresponding points or areas on both objects. Another disadvantage of these registration techniques is that these do not always yield the best registration result. The registration result can depend on the choice of the starting position since it could be the case that the registration algorithm ends in a local minimal value for the distance error instead of the global minimum of the distance error. This could be avoided by either performing the registration using a large number of starting positions or verifying all possible positions of one object with respect to the other but both would be too time-consuming. In the above-mentioned application the high-resolution digital model of the patient's dentition includes the teeth and the surrounding mucosa, while the (CB)CT-based model includes the patient's teeth and the bone, not the mucosa. Moreover the (CB)CT-based model is very often noisy and contains scatter due to metallic filling materials used in dental treatments. Therefore a fully automated registration technique that limits the influence of the “non-identical” surfaces/information onto the final matched position would be a major advantage, since it would reduce an intrinsic source of inaccuracy in computer guided implantology.
A state-of-the-art registration technique that works in case of occlusion (i.e. incomplete surface description of the object, missing surfaces) and clutter (i.e. presence of surfaces that are not part of the object surface being matched) is based on the use of spin images. As described in the thesis from Andrew Edie Johnson, Spin-images: A Representation for 3-D Surface Matching (Aug. 13, 1997 Carnegie Mellon University, Pittsburgh, Pa., USA), spin images can be used either for object recognition or for surface alignment (i.e. registration). The spin image is a local description of the shape of the object and is created by projecting 3D surface points into 2D images. For this approach a surface is described as a dense collection of 3D points and their surface normal. The spin images are based on an oriented point of the surface, i.e. a point p on the surface and the outside oriented surface normal n in this point. This oriented point defines a local coordinate system by means of the plane P through the point p oriented perpendicularly to the normal n (FIG. 1). The two coordinates of a point within this local coordinate system are α, the perpendicular distance to the normal n, and β, the signed perpendicular distance to the plane P. Thus each 3D surface point can be mapped onto the 2D coordinates of a particular basis (p,n). A consequence of this cylindrical symmetry is that points that lie on a circle parallel to the plane P and centred on n will have the same coordinates (α,β) with respect to the basis. As such a 2D point distribution is created for a specific surface point and its normal. This 2D point distribution is further simplified/discretized by creating a 2D array representation of the spin image, which quantifies the point density. This is done by creating a rectangular grid (2D array) in which the (alfa, beta) coordinates are assigned to the cells (FIG. 2) and quantifying the point density for each cell of the grid. A simple way to update the array is by incrementing the cell to which the 3D point is spin-mapped with one. A more robust way, in order to account for noise in the data, is by bilinearly interpolating the contribution of a point to the four surrounding cells in the 2D array.
This 2D point distribution is a description of the shape of a rigid object (vertices) which is independent of rigid transformations, and thus a truly object-centred shape description. Thus spin images generated for corresponding points on different surfaces will be similar, so oriented points can be matched based on a comparison of the 2D array. Since spin images can be generated for any point on the surface, no feature extraction is required.
The spin images are generated by using all of the points of the object and not only a small number of feature points. As such memory and computer power will increase with the size of the object.
The spin images need to be generated with a well-chosen cell size in order to be descriptive. A cell size of about 1 to 2 times the mesh resolution is sufficient to limit the influence of the individual point positions on the spin image and to adequately describe the global shape of the object. Also the number of rows and columns of the 2D array must be chosen in order to control the amount of global information. A decrease in the number of rows and columns will decrease the descriptiveness of the spin image since the amount of global shape included in the image is reduced, but it will also reduce the chance of clutter corrupting the spin image. Another parameter used in the spin image is the support angle, i.e. the maximum angle between the direction of the oriented point basis of a spin image and the surface normal of points that are allowed to contribute to the spin image. This parameter is used to limit the effect of self-occlusion (i.e. an object can occlude its backside) and of clutter during spin image matching.
A disadvantage of this type of spin image is the influence the direction of the normal has on the image itself. The effect of a deviation of the estimated normal relative to the exact normal, referred to as the surface normal error, on the spin image increases with increasing α and β values. Consequently, a small angular deviation of the normal can yield a large difference in the spin image, resulting in incorrect point correspondences. This is an issue in cases where data is influenced by noise and/or scatter. A spherical coordinate system, i.e. using the coordinates ρ and φ with ρ the distance of the point to the oriented point p and φ the angle between the vector from the oriented point p to the point and the tangent plane P, would result in a constant effect of the surface normal error on the coordinate φ (and no effect on the coordinate ρ). As a result these spin images may be matched more robustly in case of surface normal error. But a consequence of the spherical coordinates is that the 3D volume of cells varies (i.e. the 3D volume of cells with fixed φ increases with increasing ρ and the 3D volume of cells with fixed ρ changes with a change in φ), which would then complicate the spin image matching due to this non-uniform cell size. Due to the fact that the 3D volume of the cells varies with ρ and φ, it is impossible to generate a 2D array with uniform 3D volume. For the cylindrical coordinates the 3D volume of cells varies as well but the 3D volume only increases with increasing α. Therefore cells with constant 3D volume can be generated easily by generating a 2D array with non-equidistant cells along the α axis.
Another disadvantage of this type of spin image is the fact that the spin image depends on the resolution of the initial object. Therefore, in order to have an adequate description of the object the initial object should be uniformly meshed with a sufficient number of points (i.e. a small edge length). Thus, in case of non-uniform surface sampling the surface of the object will have to be resampled (i.e. adding or removing points) in a first step before calculating the spin images. This dependency of the spin image on the resolution also implies that a very similar sampling is needed for the different surface representations of the object in order to obtain similar spin images for two corresponding points on these different instances (surface representations) of the object.
When using spin images it is important to choose the cell size in function of the resolution of the object representation and the noise level. A cell size smaller than the noise level or the resolution of the object representation will result in spin images that are really dependent on the noise on the particular mesh, while a larger cell size will result in spin images that are less influenced by the noise and the particular mesh. So it will be important to know in advance the noise level and the object resolution to determine the optimal cell size. This implies as well that the object resolution will have to be adapted (reduced or increased by applying a remeshing algorithm or removing/adding points) in order to match with the cell size needed based on the noise.
Noisy surface data limits the use of spin images due to their dependency on the surface normal, which cannot be accurately determined in those cases. A logical approach to limit the normal dependency could be to calculate multiple spin images in each point for different normal directions and use all these data for finding correspondences. Other logical approaches are applying a smoothing to the surface before determining the normal in the surface points, or quantifying the surface normal dependency and compensating the spin image for this by for instance averaging. All these solutions will result in increased calculation time and more false positive point matches. The method of the invention does not make use of the surface normal and as such is not influenced by noise limiting the accurate calculation of the surface normal.